package com.sise.Tree;

import java.util.*;

/**
 *      145. 二叉树的后序遍历
 */
public class _145_postorderTraversal {

    /**
     *      没看懂
     */
    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Set<TreeNode> seen = new HashSet<>();                       // seen 表示看过、遍历过的意思

        while (root != null || !stack.isEmpty()) {
            if (root == null && seen.contains(stack.peek())) {      // 如果包含栈顶元素，则将栈顶值取出来 添加到结果集
                result.add(stack.pop().val);
            } else if (root == null) {                              // 当前节点为空时，那么将 栈顶元素添加到 seen，同时将栈顶元素的右节点赋值给 root
                seen.add(stack.peek());
                root = stack.peek().right;
            } else {
                stack.push(root);                                   // 节点不为空，那么将当前节点放入栈中，并且向左走
                root = root.left;
            }
        }
        return result;
    }
}